# source:https://leetcode.cn/problems/find-the-maximum-sequence-value-of-array/description/ 位运算 + DP01
class Solution:
    def maxValue(self, nums, K):
        n = len(nums)
        m = 1 << 7
        # 初始化 f 和 g，使用三维列表
        f = [[[False] * m for _ in range(K + 1)] for _ in range(n + 2)]
        g = [[[False] * m for _ in range(K + 1)] for _ in range(n + 2)]
        
        def update(x, y):
            return x or y

        # DP 求子序列前半部分的情况
        f[0][0][0] = True
        for i in range(n):
            for j in range(K + 1):
                for x in range(m):
                    if f[i][j][x]:
                        f[i + 1][j][x] = update(f[i + 1][j][x], f[i][j][x])
                        if j < K:
                            f[i + 1][j + 1][x | nums[i]] = update(f[i + 1][j + 1][x | nums[i]], f[i][j][x])

        # DP 求子序列后半部分的情况
        g[n + 1][0][0] = True
        for i in range(n + 1, 1, -1):
            for j in range(K + 1):
                for x in range(m):
                    if g[i][j][x]:
                        g[i - 1][j][x] = update(g[i - 1][j][x], g[i][j][x])
                        if j < K:
                            g[i - 1][j + 1][x | nums[i - 2]] = update(g[i - 1][j + 1][x | nums[i - 2]], g[i][j][x])

        # 枚举子序列的分界点，以及前后半的值
        ans = 0
        for i in range(K, n - K + 1):
            for x in range(m):
                for y in range(m):
                    if f[i][K][x] and g[i + 1][K][y]:
                        ans = max(ans, x ^ y)
        return ans

# source:https://leetcode.cn/problems/maximum-number-of-removable-characters/description/ 二分查找 2刷 一刷 7.30
class Solution:
    def maximumRemovals(self, s: str, p: str, removable: List[int]) -> int:
        ns, np = len(s), len(p)
        n = len(removable)
        # 辅助函数，用来判断移除 k 个下标后 p 是否是 s_k 的子序列
        def check(k: int) -> bool:
            state = [True] * ns   # s 中每个字符的状态
            for i in range(k):
                state[removable[i]] = False
            # 匹配 s_k 与 p 
            j = 0
            for i in range(ns):
                # s[i] 未被删除且与 p[j] 相等时，匹配成功，增加 j
                if state[i] and s[i] == p[j]:
                    j += 1
                    if j == np:
                        return True
            return False
        
        # 二分查找
        l, r = 0, n + 1
        while l < r:
            mid = l + (r - l) // 2
            if check(mid):
                l = mid + 1
            else:
                r = mid
        return l - 1

# source:https://leetcode.cn/submissions/detail/593909325/ 双指针 二刷 一刷 22.7.4
class Solution:
    def maxArea(self, nums: List[int]) -> int:
        ans = 0
        i, j = 0, len(nums)-1
        while i < j:
            if nums[i] < nums[j]:
                ans = max(ans, (j-i)*nums[i])
                i += 1
            else:
                ans = max(ans, (j-i)*nums[j])
                j -= 1
        return ans